graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a clique cover or partition into cliques of a given

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

is a collection of

cliques A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...

that cover the whole graph. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum for which a clique cover exists is called the clique cover number of the given graph.

Relation to coloring

A clique cover of a graph may be seen as a

graph coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...

of the

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...

of , the graph on the same vertex set that has edges between non-adjacent vertices of . Like clique covers, graph colorings are partitions of the set of vertices, but into subsets with no adjacencies ( independent sets) rather than cliques. A subset of vertices is a clique in if and only if it is an independent set in the complement of , so a partition of the vertices of is a clique cover of if and only if it is a coloring of the complement of .

Computational complexity

The clique cover problem in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

is the

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

ic problem of finding a minimum clique cover, or (rephrased as a

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

) finding a clique cover whose number of cliques is below a given threshold. Finding a minimum clique cover is

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

, and its decision version is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

. It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems". The equivalence between clique covers and coloring is a reduction that can be used to prove the NP-completeness of the clique cover problem from the known NP-completeness of graph coloring.

In special classes of graphs

Perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

s are defined as graphs in which, for every

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

, the chromatic number (minimum number of colors in a coloring) equals the size of the

maximum clique In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of th ...

. According to the weak perfect graph theorem, the complement of a perfect graph is also perfect. Therefore, the perfect graphs are also the graphs in which, for every induced subgraph, the clique cover number equals the size of the

maximum independent set In mathematical analysis, the maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...

. It is possible to compute the clique cover number in perfect graphs in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

. Another class of graphs in which the minimum clique cover can be found in polynomial time are the

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

s. In these graphs, every clique cover consists of a matching (a set of disjoint pairs of adjacent vertices) together with

singleton set In mathematics, a singleton (also known as a unit set or one-point set) is a set with exactly one element. For example, the set \ is a singleton whose single element is 0. Properties Within the framework of Zermelo–Fraenkel set theory, the a ...

s for the remaining unmatched vertices. The number of cliques equals the number of vertices minus the number of matched pairs. Therefore, in triangle-free graphs, the minimum clique cover can be found by using an algorithm for

maximum matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is a ...

. The optimum partition into cliques can also be found in polynomial time for graphs of bounded

clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of ...

. These include, among other graphs, the

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s and

distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the Distance (graph theory), distances in any connected graph, connected induced subgraph are the same as ...

s, which are also classes of perfect graphs. The clique cover problem remains NP-complete on some other special classes of graphs, including the

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s and unit disk graphs.

Approximation

The same

hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of approximation algorithms by pro ...

results that are known for graph coloring also applies to clique cover. Therefore, unless

P = NP The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that ...

, there can be no

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

for any that, on -vertex graphs, achieves an

approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...

better than . In graphs where every vertex has at most three neighbors, the clique cover remains NP-hard, and there is a constant such that it is NP-hard to approximate with

or better. Nevertheless, in

it is possible to find an approximation with a ratio of 5/4. That is, this approximation algorithm finds a clique cover whose number of cliques is no more than 5/4 times the optimum.. Baker's technique can be used to provide a

polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an inst ...

for the problem on planar graphs.

References

{{reflist Graph theory objects NP-complete problems Computational problems in graph theory

Relation to coloring

Computational complexity

In special classes of graphs

Approximation

Related problems

References